package com.linyaonan.leetcode.medium._61;

/**
 * 给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
 *
 * 输入：head = [0,1,2], k = 4
 * 输出：[2,0,1]
 *  
 *
 * 提示：
 *
 * 链表中节点的数目在范围 [0, 500] 内
 * -100 <= Node.val <= 100
 * 0 <= k <= 2 * 109
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/rotate-list
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
class Solution {

    /**
     * 思路1：首先考虑到k比链表长度要大得多，那么首先计算出链表的长度，然后k进行取余
     *
     * 将链表使用双指针的方法，快指针首先走到倒数k位置，然后前一个位置断链，尾部连接头指针即可
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode rotateRight(ListNode head, int k) {
        // 特殊边界
        if (head == null || head.next == null) {
            return head;
        }

        ListNode f = head;
        ListNode l = head;
        ListNode e = l;
        ListNode s = l;

        int count = 0;
        while (head != null) {
            count++;
            head = head.next;
        }
        int move = k % (count);

        if (move == 0) {
            return f;
        }

        // 找到移动到节点的前一个
        while (move != 0) {
            f = f.next;
            move--;
        }

        while (f.next != null) {
            f = f.next;
            l = l.next;
        }
        s = l.next;
        ListNode result = s;
        l.next = null;
        while (s.next != null) {
            s = s.next;
        }
        s.next = e;

        return result;

    }
}